#complexite 
division := proc (A,B,V)
	local delta, At, Rt, tmp, X, Q, R;
	At := 0;
	Rt := A;
	X := V;
	while degree(Rt)>=degree(B) do
		delta := degree(Rt)-degree(B);
		tmp := (lcoeff(Rt)/lcoeff(B))*X^delta;
		At := expand(At + tmp);
		Rt := expand(Rt - (tmp*B));
	od;
	Q:=At;
	R:=Rt;
	(Q,R);
end;

euclide := proc (A,B,V)
	local A1, A2, i;
	if(degree(A)<degree(B)) then
		euclide(B,A,V);
	fi;
	A1 := A;
	A2 := B;
	while A2 <> 0 do
		(A1,A2) := division(A1,A2,V);
	od;
	A1;
end;
